/*
 * Created by guoyh on Mon Dec 12 2022 08:48:29
 * leetcode NO.148 https://leetcode.cn/problems/sort-list/ 
 */

#include <iostream>
#include <gtest/gtest.h>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head) return nullptr;

        vector<int> v;
        ListNode* p = head;
        while(p){
            v.push_back(p->val);
            p = p->next;
        }
        sort(v.begin(), v.end());

        //尾插法构建链表
        ListNode* dummy = new ListNode();
        ListNode* tail = dummy;
        for(auto it = v.begin(); it != v.end(); it++){
            ListNode* newNode = new ListNode(*it);
            newNode->next = nullptr;
            tail->next = newNode;
            tail = tail->next;
        }
        return dummy->next;

    }
};

// 尾插法创建链表
ListNode* build_linklist(vector<int> v){
    ListNode* dummy = new ListNode();
    ListNode* tail = dummy;
    for(int i : v){
        ListNode* newNode = new ListNode(i);
        newNode->next = nullptr;
        tail->next = newNode;
        tail = tail->next;
    }
    return dummy->next;
}


void print(ListNode* l){
    while(l){
        cout<<l->val<<",";
        l = l->next;
    }
    cout<<endl;
}

int add(int a, int b) {
    return a + b;
}

TEST(MyTest, AddTest) {
    EXPECT_EQ(add(1, 2), 3);
}

TEST(MYtest, Sort1){
    vector<int> v = {3,2,-2,4,5};
    ListNode* l = build_linklist(v);
    Solution slu;
    ListNode* res = slu.sortList(l);
    print(res);
    EXPECT_NE(res, nullptr);
}

TEST(MYtest, Sort2){
    vector<int> v;
    ListNode* l = build_linklist(v);
    Solution slu;
    ListNode* res = slu.sortList(l);
    print(res);
    EXPECT_EQ(res, nullptr);
}

int main(int argc, char *argv[]) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}
